/*
 * UniformCostSearch.java
 * 
 * TCSS 435 - Autumn 2012
 * Homework 1
 */

import java.util.*;
import java.util.Map.Entry;

/**
 * A uniform cost search.
 * 
 * @author Dallas Rosson
 * @version Autumn 2012
 */
public class UniformCostSearch {
	
	/**
	 * A uniform cost search.
	 * 
	 * @param start The starting state with cost.
	 * @param goal The goal to be found.
	 * @return A List representing the path taken to reach the node containing the goal state.
	 */
	public static List<StateWithCost> solve(final StateWithCost start, final StateWithCost goal) {
		// FIFO collection of nodes that have not been explored.
		PriorityQueue<Node> frontier = new PriorityQueue<>();
		// Collection (with fast search) holding nodes that have been explored or
		// are already in the frontier.  Each node maps to its parent node, for the
		// purposes of tracing and displaying the solution path.
		Map<Node,Node> explored = new HashMap<>();
		// The total number of nodes explored.
		int nodesExplored = 0;
		// The total number of nodes that have been in the frontier.
		int nodesInFrontier = 0;
		// The total number of nodes created.
		int nodesCreated = 0;
		// The path to the goal node.
		List<StateWithCost> path = new LinkedList<StateWithCost>();

		Node startNode = new Node(start, 0);
		
		frontier.add(startNode);
		explored.put(startNode, null);
		nodesInFrontier++;
			
outer:	while (!frontier.isEmpty()) {
		
			Node node = frontier.remove();
			nodesExplored++;
			
			Iterator<Entry<StateWithCost, Double>> it = node.getStateWithCost().getNeighborsWithCost().entrySet().iterator();
						
			while (it.hasNext()) {
				
				Map.Entry<StateWithCost, Double> entry = it.next();
				Node newChild = new Node(entry.getKey(), entry.getValue());
				
				nodesCreated++;
				
				boolean isNotExplored = true;
				
				Iterator<Entry<Node, Node>> itE = explored.entrySet().iterator();
				
				while (itE.hasNext()) { // Check to see if the child has already been explored.
							
					if (itE.next().getKey().equals(newChild)) {
						isNotExplored = false;
						break;
					}
				}
				
				if (isNotExplored) {
					
					if (!(frontier.contains(newChild))) { // Ensure the frontier does not already contain the child.
										
						double newCost = node.getCost() + newChild.getCost();
						
						newChild.setCost(newCost);
						
						frontier.add(newChild);
						explored.put(newChild, node);
						nodesInFrontier++;
						
					} else if (frontier.contains(newChild)) { // If already in frontier, keep highest value.
													
						PriorityQueue<Node> tempFrontier = new PriorityQueue<>();
						
						for (int i = 0; i < frontier.size(); i++) {
							
							if (!frontier.peek().equals(newChild)) {
								
								tempFrontier.add(frontier.remove());
							} else {
																
								frontier.remove();
								frontier.add(newChild);
								
								while (!tempFrontier.isEmpty()) {
									
									frontier.add(tempFrontier.remove());
								}		
								
								break;
							}								
						}
					}
					
					if (newChild.getStateWithCost().equals(goal)) {
													
						path = createPath(newChild, explored);
						displaySolutionPath(path);
						break outer;
					}
				} 			
			}
							
			System.out.println("Frontier: \n" + frontier.toString());
			System.out.println("explored: \n" + explored.toString() + "\n");
		}
		
		System.out.println("   Nodes explored: " + nodesExplored);
		System.out.println("Nodes in frontier: " + nodesInFrontier);
		System.out.println("    Nodes created: " + nodesCreated);
		
		return path;
	}
	
	public static void displaySolutionPath(List<StateWithCost> path) {
		
		System.out.println("\n\n\n\n\n");
		System.out.println("---------- Solution Found ----------");
		

		for (StateWithCost puzzle : path)
			System.out.println(puzzle);
		System.out.println("Solution in " + (path.size() - 1) + " moves.");
	}
	
	/**
	 * Creates a list representing the path to the node holding the goal state.
	 * 
	 * @param node The node that contains the goal state.
	 * @param parentMap The collection holding the nodes of the current search path.
	 * @return A list representing the path to the node holding the goal state.
	 */
	private static LinkedList<StateWithCost> createPath(Node node, final Map<Node, Node> parentMap) {
		
		LinkedList<StateWithCost> path = new LinkedList<StateWithCost>();
		
		while (node != null) {
			path.addFirst(node.getStateWithCost());
			node = parentMap.get(node);
		}
		return path;
	}
}

class Node implements Comparable<Node>{
	
	// The state with cost value of this node.
	private StateWithCost stateWithCost;
	
	// The total cost of this node.
	private double cost;
	
	/**
	 * A Node.
	 * 
	 * @param the_swc The StateWithCost value of this Node.
	 * @param the_cost The total cost value of this node.
	 */
	public Node(StateWithCost the_swc, double the_cost) {
		
		stateWithCost = the_swc;
		cost = the_cost;
	}
	
	/**
	 * @return The StateWithCost value of this Node.
	 */
	public StateWithCost getStateWithCost() {
		
		return stateWithCost;
	}
	
	/**
	 * @return The total cost value of this Node.
	 */
	public double getCost() {
		
		return cost;
	}
	
	/**
	 * Sets the cost to the passed in value.
	 * 
	 * @param newCost the desired cost.
	 */
	public void setCost(final double newCost) {
		
		cost = newCost; 
	}
	
	@Override
	public String toString() {
		
		return stateWithCost.toString();
	}
	
	/**
	 * {@inheritDoc}
	 */
	@Override
	public int hashCode() {
		
		return stateWithCost.toString().hashCode();
	}
	
	/**
	 * {@inheritDoc}
	 */
	@Override
	public int compareTo(final Node theNode) {
		
		int retVal = 0;
		
		if (cost < theNode.getCost()) {
			
			retVal = -1;
			
		} else if (cost > theNode.getCost()) {
			
			retVal = 1;
		}
		
		return retVal;
	}
	
	/**
	 * An equality method for Node.
	 * 
	 * @param theNode The Node to be compared to.
	 * @return If equal, true. 
	 * </p>If not equal, false.
	 */
	public boolean equals(final Node theNode) {
		
		boolean retVal = false;
		
		if (toString().equals(theNode.toString())) {
			
			retVal = true;
		}
		
		return retVal;
	}
	
	
}
